#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_

#include <cstdbool>
#define ElementType void*



typedef void (*FuncCallback)(void*,void*);
// 节点类
class BTNode 
{
public:
    ElementType data; // 数据域
    BTNode *left; // 左孩子
    BTNode *right; // 右孩子
    BTNode *parent; // 双亲节点指针

    // 构造函数
    BTNode(ElementType element = NULL, BTNode *left = NULL, BTNode *right = NULL, BTNode *parent = NULL):data(element), left(left), right(right), parent(parent) {}
};

// 二叉搜索树类
class BSTree 
{
public:

    // 构造函数
    BSTree() : root(NULL) {}

    // 析构函数
    ~BSTree() {
        DeleteTree;
    }

    // 获取节点的值
    ElementType GetNodeData(BTNode *n);
    // 初始化二叉树
    BSTree* InitBSTree();
    // 往树中插入一个元素
    void InsertElement(ElementType element, int(*funcPtr)(ElementType, ElementType));

    // 前序遍历
    void TravelPrev(BTNode *node, void(*funcPtr)(ElementType));
    // 中序遍历
    void TravelMid(BTNode *node, void(*funcPtr)(ElementType));
    // 后序遍历
    void TravelPost(BTNode *node, void(*funcPtr)(ElementType));

    // 查找树中节点
    BTNode *FindByElement(ElementType element, int(*funcPtr)(ElementType, ElementType));

    // 删除一个节点
    void RemoveByElement(ElementType element, int(*funcPtr)(ElementType, ElementType)); 
    int GetTreeHeight(BSTree *tree);
    // 插入树
    void* InsertTree(ElementType element, int(*funcPtr)(ElementType, ElementType));
    // 删除树
    void* DeleteTree(ElementType element, int(*funcPtr)(ElementType, ElementType));

private:
    BTNode *root; // 根节点
    FuncCallback funcPtr;
};

#endif
